package NiuKe;

import java.util.*;

/**
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]]
 * 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。
 * 请你返回所有和为 0 且不重复的三元组。
 */
public class SumThreeNumbers {
    public static void main(String[] args) {
        List<List<Integer>> lists = threeSum(new int[]{0,0,0});
        System.out.println(lists);
    }
    public static List<List<Integer>> threeSum(int[] nums) {
        // 数组排序
        Arrays.sort(nums);
        ArrayList<List<Integer>> result = new ArrayList<>();
        if(nums[0] > 0 || nums[nums.length-1] < 0){
            return result;
        }
        if(nums[0] == 0 && nums[nums.length] == 0){
            ArrayList<Integer> re = new ArrayList<>();
            re.add(0);
            re.add(0);
            re.add(0);
            result.addAll(Collections.singleton(re));
            return result;
        }
        int left = 0;
        while (nums[left] < 0){
            int point;
            int right = nums.length - 1;
            while (nums[right] > 0) {
                int res = 0 - nums[left] - nums[right];
                if (res < 0) {
                    point = left + 1;
                    while (nums[point] <= 0) {
                        if (nums[point] == res) {
                            result.add(Arrays.asList(nums[left], nums[point], nums[right]));
                            break;
                        }
                        point++;
                    }
                } else {
                    point = right - 1;
                    while (nums[point] >= 0) {
                        if (nums[point] == res) {
                            result.add(Arrays.asList(nums[left], nums[point], nums[right]));
                            break;
                        }
                        point--;
                    }
                }
                right--;
            }
            if(nums[left+1] == nums[left]){
                left += 2;
            }else {
                left++;
            }
        }
        return result;
    }
}
